package Leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
 * 例如，给出 n = 3，生成结果为：
 * [
 *   "((()))",
 *   "(()())",
 *   "(())()",
 *   "()(())",
 *   "()()()"
 * ]
 */
public class L22_括号生成 {
    /**
     * 典型的回溯问题，跟N皇后的一样   记得算法的框架
     * 回溯算法(){
     *     终止条件； 返回
     *
     *     过滤不合法的
     *     做选择
     *     回溯
     *     撤销选择
     * }
     * 这题的一点是，左括号的数量一定是>右括号的
     *
     * 这道题要注意，用stringbuilder 一定要注意，做撤回。
     */
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n==0) return res;
        StringBuilder sb = new StringBuilder("");
        backstrace(res, sb, 0,0, n);
        return res;
    }

    private void backstrace(List<String> res, StringBuilder sb, int left,int right, int n){
        if(sb.length() == 2*n){
            res.add(sb.toString());
            return;
        }
        //左括号的数量只要比n小就行了， 另外，要注意是从0开始计数的，这里<就行了
        if(left < n){
            backstrace(res, sb.append("("), left+1, right, n);
            sb.deleteCharAt(sb.length()-1);//这个一定要撤回上面的操作，不然会出问题
            //使用字符串没问题是因为，字符串都是复制出来的
        }
        //这里要注意，这里踩坑了，右括号的数量，一定比左括号少
        if(right < left){
            backstrace(res, sb.append(")"), left, right+1, n);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    public static void main(String[] args){
        L22_括号生成 a = new L22_括号生成();
        a.generateParenthesis(3);
    }
}
